class ArrayAndStringAlgorithms:
    @staticmethod
    def two_pointer(nums, target):
        """
        双指针算法

        参数:
        nums (List[int]): 输入的数组
        target (int): 目标值

        返回:
        List[int]: 找到的目标值的索引

        实现步骤:
        1. 定义左右指针，初始位置分别为数组的首尾
        2. 循环遍历，直到左右指针相遇
        3. 如果左右指针指向的元素之和等于目标值，返回左右指针的索引
        4. 如果左右指针指向的元素之和小于目标值，左指针右移一位
        5. 如果左右指针指向的元素之和大于目标值，右指针左移一位
        6. 如果循环结束都没有找到目标值，返回空列表

        """

        # 步骤 1: 定义左右指针，初始位置分别为数组的首尾
        left = 0
        right = len(nums) - 1

        # 步骤 2: 循环遍历，直到左右指针相遇
        while left < right:
            # 步骤 3: 如果左右指针指向的元素之和等于目标值，返回左右指针的索引
            if nums[left] + nums[right] == target:
                return [left, right]
            # 步骤 4: 如果左右指针指向的元素之和小于目标值，左指针右移一位
            elif nums[left] + nums[right] < target:
                left += 1
            # 步骤 5: 如果左右指针指向的元素之和大于目标值，右指针左移一位
            else:
                right -= 1

        # 步骤 6: 如果循环结束都没有找到目标值，返回空列表
        return []


    @staticmethod
    def sliding_window(nums, k):
        """
        滑动窗口算法

        参数:
        nums (List[int]): 输入的数组
        k (int): 窗口大小

        返回:
        List[int]: 窗口中的最大值列表

        实现步骤:
        1. 定义窗口的起始位置和结果列表
        2. 初始化双端队列，用于维护窗口中的最大值索引
        3. 遍历数组，维护窗口的大小为k
        4. 检查队列中的最大值索引是否超出窗口范围，若超出则移除
        5. 将当前元素与队列尾部的元素比较，若当前元素大于等于队列尾部的元素，则将队列尾部的元素弹出，直到当前元素小于队列尾部的元素
        6. 将当前元素的索引添加到队列尾部
        7. 若窗口已经形成，将队列头部的元素（即窗口中的最大值）添加到结果列表中
        8. 返回结果列表

        """
        import collections

        # 步骤 1: 定义窗口的起始位置和结果列表
        start = 0
        result = []

        # 步骤 2: 初始化双端队列，用于维护窗口中的最大值索引
        max_queue = collections.deque()

        # 步骤 3: 遍历数组，维护窗口的大小为k
        for end in range(len(nums)):
            # 步骤 4: 检查队列中的最大值索引是否超出窗口范围，若超出则移除
            if max_queue and max_queue[0] < end - k + 1:
                max_queue.popleft()

            # 步骤 5: 将当前元素与队列尾部的元素比较，若当前元素大于等于队列尾部的元素，则将队列尾部的元素弹出，直到当前元素小于队列尾部的元素
            while max_queue and nums[end] >= nums[max_queue[-1]]:
                max_queue.pop()

            # 步骤 6: 将当前元素的索引添加到队列尾部
            max_queue.append(end)

            # 步骤 7: 若窗口已经形成，将队列头部的元素（即窗口中的最大值）添加到结果列表中
            if end >= k - 1:
                result.append(nums[max_queue[0]])

            # 步骤 8: 更新窗口的起始位置
            start += 1

        # 步骤 9: 返回结果列表
        return result



    @staticmethod
    def sorting(nums):
        """
        排序算法

        参数:
        nums (List[int]): 输入的数组

        返回:
        List[int]: 排序后的数组

        实现步骤:
        1. 使用快速排序算法对数组进行排序
        2. 返回排序后的数组

        """

        # 步骤 1: 使用快速排序算法对数组进行排序
        def quicksort(arr):
            if len(arr) <= 1:
                return arr
            pivot = arr[len(arr) // 2]
            left = [x for x in arr if x < pivot]
            middle = [x for x in arr if x == pivot]
            right = [x for x in arr if x > pivot]
            return quicksort(left) + middle + quicksort(right)

        sorted_nums = quicksort(nums)

        # 步骤 2: 返回排序后的数组
        return sorted_nums

    @staticmethod
    def hash_table(words):
        """
        哈希表算法

        参数:
        words (List[str]): 输入的字符串列表

        返回:
        List[str]: 出现频率最高的单词列表

        实现步骤:
        1. 使用哈希表统计每个单词的出现频率
        2. 找到出现频率最高的单词
        3. 返回出现频率最高的单词列表

        """

        # 步骤 1: 使用哈希表统计每个单词的出现频率
        word_count = {}
        for word in words:
            word_count[word] = word_count.get(word, 0) + 1

        # 步骤 2: 找到出现频率最高的单词
        max_count = max(word_count.values())

        # 步骤 3: 返回出现频率最高的单词列表
        most_frequent_words = [word for word, count in word_count.items() if count == max_count]

        return most_frequent_words

if __name__ == '__main__':
    # 示例调用双指针算法
    nums = [2, 7, 11, 15]
    target = 9
    result_two_pointer = ArrayAndStringAlgorithms.two_pointer(nums, target)
    print("双指针算法输入:", nums, target)
    print("双指针算法输出:", result_two_pointer)
    """
    示例输出结果:
    双指针算法输入: [2, 7, 11, 15] 9
    双指针算法输出: [0, 1]
    """

    # 示例调用滑动窗口算法
    nums = [1, 3, -1, -3, 5, 3, 6, 7]
    k = 3
    result_sliding_window = ArrayAndStringAlgorithms.sliding_window(nums, k)
    print("滑动窗口算法输入:", nums, k)
    print("滑动窗口算法输出:", result_sliding_window)
    """
    示例输出结果:
    滑动窗口算法输入: [1, 3, -1, -3, 5, 3, 6, 7] 3
    滑动窗口算法输出: [3, 3, 5, 5, 6, 7]
    """

    # 示例调用排序算法
    nums = [5, 2, 9, 1, 7]
    result_sorting = ArrayAndStringAlgorithms.sorting(nums)
    print("排序算法输入:", nums)
    print("排序算法输出:", result_sorting)
    """
    示例输出结果:
    排序算法输入: [5, 2, 9, 1, 7]
    排序算法输出: [1, 2, 5, 7, 9]
    """

    # 示例调用哈希表算法
    words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
    result_hash_table = ArrayAndStringAlgorithms.hash_table(words)
    print("哈希表算法输入:", words)
    print("哈希表算法输出:", result_hash_table)
    """
    示例输出结果:
    哈希表算法输入: ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
    哈希表算法输出: ['apple']
    """

